XJOI200808 题解

A

---

咕咕

B

---

部分分提醒正解。考虑 n <= 2 时，设 $a_1 = A$, $a_2 = B$，那么 A 先取完时期望个数就是 $a_1 + \sum\limits_{i = 0}^{B - 1} \frac{C(A - 1 + i, i)}{2^{B + 1}} i$，B 先取完时就是 $a_1 + \sum\limits_{i = 0}^{A - 1} \frac{C(B - 1 + i, i)}{2^{B + 1}} B$。

根据期望的线性性质，$ans = (\sum\limits_{i = 2}^n \{第 i 个被拿的期望个数\}) + a_1$。现在就是怎么求解每种球的期望个数。我们设第 i 种球的期望个数为 $f_i$。

注意到选颜色是等概率的。本题中唯一的限制就是第一种球必须取完，那么 $f_i$ 只与在第一种球取完前 取了多少个第 i 种球有关，取其他球对它们没有影响，而且它们被取的概率是相同的，那就等价于之前的部分分算法。这样是 60 分。

考虑优化：将上面的方法看作从 $(a_1, a_i)$ 出发每次随机向下或向左走一步，直到走到坐标轴。走到 $(0, a)$ 的贡献是 $a_i - a$，走到 $(a, 0)$ 的贡献是 $a_i$，就能列出贡献柿子：

$$f_i = \sum\limits_{j = 0}^{a_i - 1} \frac{C(a_1 - 1 + j, j)}{2^{a_1 + j}} \times j + a_i(1 - \sum\limits_{j = 0}^{a_i - 1} \frac{C(a_1 - 1 + j, j)}{2^{a_1 + j}})$$

容易发现 $a_i$ 增加 1 的时候 两部分的贡献分别都只会增加一项，可以 O(1) 算！这样就能线性求解了，是 O(值域) 的。

C

---

咕咕